﻿#include <stdio.h>
#include <stdlib.h>

// 定义结构体
typedef struct celltype {
    int data;
    struct celltype* lchild;
    struct celltype* rchild;
} BSTNode;

typedef BSTNode* BST;

// 插入节点
void insert(BST* root, int value) {
    if (*root == NULL) {
        *root = (BST)malloc(sizeof(BSTNode));
        (*root)->data = value;
        (*root)->lchild = (*root)->rchild = NULL;
    }
    else {
        if (value < (*root)->data) {
            insert(&((*root)->lchild), value);
        }
        else {
            insert(&((*root)->rchild), value);
        }
    }
}

// 查找节点
BST search(BST root, int key, int* sum, int level) {
    if (root == NULL || root->data == key) {
        *sum += level;
        return root;
    }
    if (key < root->data) {
        return search(root->lchild, key, sum, level + 1);
    }
    return search(root->rchild, key, sum, level + 1);
}

// 删除节点
BST deleteNode(BST root, int key) {
    if (root == NULL) return root;
    if (key < root->data) {
        root->lchild = deleteNode(root->lchild, key);
    }
    else if (key > root->data) {
        root->rchild = deleteNode(root->rchild, key);
    }
    else {
        if (root->lchild == NULL) {
            BST temp = root->rchild;
            free(root);
            return temp;
        }
        else if (root->rchild == NULL) {
            BST temp = root->lchild;
            free(root);
            return temp;
        }
        BST temp = root->rchild;
        while (temp->lchild != NULL) {
            temp = temp->lchild;
        }
        root->data = temp->data;
        root->rchild = deleteNode(root->rchild, temp->data);
    }
    return root;
}

// 计算BST的平均查找长度
float calculateAverageSearchLength(BST root, int* sum, int* count, int level) {
    if (root != NULL) {
        (*count)++;
        calculateAverageSearchLength(root->lchild, sum, count, level + 1);
        calculateAverageSearchLength(root->rchild, sum, count, level + 1);
    }
    return (float)(*sum) / (*count);
}

// 折半查找函数
int binarySearch(int arr[], int left, int right, int key, int* count) {
    while (left <= right) {
        (*count)++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1; // 查找失败
}

int main() {
    // 建立BST
    BST bst = NULL;
    int testData[1024];
    // 初始化测试数据
    for (int i = 0; i < 1024; ++i) {
        testData[i] = 2 * i + 1;
    }
    // 插入测试数据到BST
    for (int i = 0; i < 1024; ++i) {
        insert(&bst, testData[i]);
    }
    // 执行查找成功和查找失败的平均查找长度
    int sumSuccess = 0, sumFail = 0, countSuccess = 0, countFail = 0;
    // 计算查找成功的平均查找长度
    for (int i = 0; i < 1024; ++i) {
        int temp = 0;
        BST result = search(bst, testData[i], &temp, 1);
        sumSuccess += temp;
        countSuccess++;
    }
    // 计算查找失败的平均查找长度
    for (int i = 0; i < 1024; ++i) {
        int temp = 0;
        BST result = search(bst, testData[i] + 1, &temp, 1);
        sumFail += temp;
        countFail++;
    }

    printf("平均查找成功长度：%f\n", calculateAverageSearchLength(bst, &sumSuccess, &countSuccess, 0));
    printf("平均查找失败长度：%f\n", calculateAverageSearchLength(bst, &sumFail, &countFail, 0));

    // 测试折半查找
    int key = 21; // 假设要查找的值为2001
    int countBinary = 0;
    int index = binarySearch(testData, 0, 1023, key, &countBinary);

    // 输出结果
    if (index != -1) {
        printf("折半查找成功：值 %d 在数组中的索引为 %d，查找长度为 %d\n", key, index, countBinary);
    }
    else {
        printf("折半查找失败：值 %d 不在数组中，查找长度为 %d\n", key, countBinary);
    }

    // 释放内存
    free(bst);

    return 0;
}
